Monochromatic arithmetic progressions in binary words associated with pattern sequences

Abstract: Let $e_v(n)$ denote the number of occurrences of a pattern $v$ in the binary expansion of $n \in \mathbb{N}$. In the talk we consider monochromatic arithmetic progressions in the class of words $(e_v(n) \bmod{2})_{n \geq 0}$ over $\{0,1\}$, which includes the Thue--Morse word $\mathbf{t}$ ($v=1$) and a variant of the Rudin--Shapiro word $\mathbf{r}$ ($v=11$). So far, the problem of exhibiting long progressions and finding an upper bound on their length has mostly been studied for $\mathbf{t}$ and certain generalizations. We show that analogous results hold for $\mathbf{r}$. In particular, we prove that a monochromatic arithmetic progression of difference $d \geq 3$ starting at $0$ in $\mathbf{r}$ has length at most $(d+3)/2$, with equality infinitely often. We also compute the maximal length of progressions of differences $2^k-1$ and $2^k+1$. Some weaker results for a general pattern $v$ are provided as well.

number theory

Audience: researchers in the discipline

Combinatorial and additive number theory (CANT 2022)